/**
 * Exercise 3.25
 * ------------------
 * Write a code fragment that determines the number of nodes that are
 * between the nodes referenced by two given pointers `x` and `t` to nodes
 * on a circular list.
 * --------------------------
 * 
 * 
 * 
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int Item;
typedef struct node *link;

struct node {
    Item item;
    link next;
};



int count(link x, link t);
void test_single_node();
void test_adjacent_nodes();
void test_multiple_nodes();
void test_t_before_x();

int main(int argc, char **argv) {
    test_single_node();
    test_adjacent_nodes();
    test_multiple_nodes();
    test_t_before_x();
    return 0;
}

int count(link x, link t){
    int count = 0;
    link curr = x->next;
    link end = t;
    while (curr != end){
        count++;
        curr = curr->next;
    }

    return count;
    
}

void test_single_node() {
    link x = malloc(sizeof(struct node));
    x->next = x; // 自环
    assert(count(x, x) == 0);
    free(x);
}

void test_adjacent_nodes() {
    link t = malloc(sizeof(struct node));
    link x = malloc(sizeof(struct node));
    x->next = t;
    t->next = x; // 形成环
    assert(count(x, t) == 0);
    free(x);
    free(t);
}

void test_multiple_nodes() {
    link t = malloc(sizeof(struct node));
    link b = malloc(sizeof(struct node));
    link a = malloc(sizeof(struct node));
    link x = malloc(sizeof(struct node));
    
    x->next = a;
    a->next = b;
    b->next = t;
    t->next = x; // 形成环
    
    assert(count(x, t) == 2);
    
    free(x);
    free(a);
    free(b);
    free(t);
}

void test_t_before_x() {
    link t = malloc(sizeof(struct node));
    link b = malloc(sizeof(struct node));
    link x = malloc(sizeof(struct node));
    link a = malloc(sizeof(struct node));
    
    t->next = b;
    b->next = x;
    x->next = a;
    a->next = t; // 形成环
    
    assert(count(x, t) == 1);
    
    free(t);
    free(b);
    free(x);
    free(a);
}